package cn.sjtu.algorithm.array_sort;

import java.util.Arrays;

/**
 * @author syo 2319615164@qq.com
 * @description 堆排序
 * @date 2024/5/16
 * @Copyright syo
 */
public class HeapSort {
    public static void main(String[] args) {
        int[] nums = {9, 1, 8, 2, 7, 3, 6, 4, 5, 0};
        heapSort(nums);
        System.out.println(Arrays.toString(nums));
    }

    public static void heapSort(int[] nums) {
        buildHeap(nums, nums.length);
        for (int i = 0; i < nums.length - 1; i++) {
            swap(nums, 0, nums.length - 1 - i);
            maxHeapify(nums, 0, nums.length - 1 - i);
        }
    }

    public static void buildHeap(int[] nums, int heapSize) {
        for (int i = heapSize / 2; i >= 0; i--) {
            maxHeapify(nums, i, heapSize);
        }
    }

    public static void maxHeapify(int[] nums, int root, int heapSize) {
        int l = root * 2 + 1;
        int r = root * 2 + 2;
        int large = root;

        if (l < heapSize && nums[l] > nums[large]) {
            large = l;
        }

        if (r < heapSize && nums[r] > nums[large]) {
            large = r;
        }

        if (large != root) {
            swap(nums, root, large);
            maxHeapify(nums, large, heapSize);
        }
    }

    public static void swap(int[] nums, int l, int r) {
        int temp = nums[l];
        nums[l] = nums[r];
        nums[r] = temp;
    }
}
